#include "leecode.h"

#include <vector>
#include <algorithm>
#include <string>
#include <array>
#include <set>

using namespace std;

class Solution {
public:
  int numDecodings(string s) {
    input_len = s.length();
    return decodings(s, 0);
  }

  int decodings(string& s, int pos) {
    if(pos >=  input_len)
       return 0;
    else if(m_results.find(pos) != m_results.end()){
      return m_results[pos];
    } else if(pos == input_len - 1) {
      string temp = s.substr(pos, 1);
      if(m_dict.find(temp) != m_dict.end()) {
        m_results[pos] = 1;
        return 1;
      } else
        return 0;

    } else if(pos == input_len - 2) {
      string temp1 = s.substr(pos, 1);
      int ret = 0;
      if(m_dict.find(temp1) != m_dict.end()) {
        string temp2 = s.substr(pos+1, 1);
        if(m_dict.find(temp2) != m_dict.end()) {
          ret ++;
        }
      }

      string temp3 = s.substr(pos, 2);
      if(m_dict.find(temp3) != m_dict.end()) {
        ret ++;
      }
      m_results[pos] = ret;
      return ret;
    } else {
      int ret1 = 0, ret2 = 0;

      string temp1 = s.substr(pos, 1);
      if(m_dict.find(temp1) != m_dict.end())
        ret1 = decodings(s, pos+1);

      string temp2 = s.substr(pos, 2);
      if(m_dict.find(temp2) != m_dict.end())
        ret2 = decodings(s, pos+2);
      m_results[pos] = ret1 + ret2;
      return  ret1 + ret2;
    }
    return 0;
  }

  Solution() {
    m_dict = {"1", "2", "3", "4", "5", "6", "7",
             "8", "9", "10", "11", "12", "13", "14",
             "15", "16", "17", "18", "19", "20", "21", "22",
             "23", "24", "25", "26"};
  }

  int input_len = 0 ;
  set<string> m_dict;
  map<int, int> m_results;
};

void TestInput91(const std::string& input) {
  Solution s;
  int ret = s.numDecodings(input);
  std::cout << "input is : " << input << endl;
  std::cout << "result is: " << ret << endl;
}

TEST(numDecodings, n1) {
  GTEST_SKIP();
//  TestInput("11106");
  TestInput91("111111111111111111111111111111111111111111111");
}
